/**  
 
* @author xuzhixiang 

* @date 2018年12月11日  

*/
package leetcode;

/**
 * 
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * 
 * @author xuzhixiang
 * @date 2018年12月11日下午12:20:55
 */
public class Demo21 {
	public static void main(String args[]) {
		Solution solution = new Solution();

		ListNode listNode1 = new ListNode(1);
		ListNode listNode2 = new ListNode(2);
		ListNode listNode3 = new ListNode(4);

		ListNode listNode4 = new ListNode(1);
		ListNode listNode5 = new ListNode(3);
		ListNode listNode6 = new ListNode(4);

		listNode2.next = listNode3;
		listNode1.next = listNode2;

		// while (listNode1 != null) {
		// System.out.print("->" + listNode1.val);
		// listNode1 = listNode1.next;
		// }
		// System.out.println();

		listNode5.next = listNode6;
		listNode4.next = listNode5;

		// while (listNode4 != null) {
		// System.out.print("->" + listNode4.val);
		// listNode4 = listNode4.next;
		// }
		// System.out.println();

		ListNode node = solution.mergeTwoLists(listNode1, listNode4);

		while (node != null) {
			System.out.print("->" + node.val);
			node = node.next;
		}

	}
}

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

class Solution {
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

		// 定义两个指针记录两个链表的当前位置
		ListNode result = new ListNode(0);
		ListNode res = result;
		while (true) {

			if (l1 == null && l2 == null) {
				break;
			}

			if (l1 == null && l2 != null) {

				result.next = l2;
				break;

			} else if (l1 != null && l2 == null) {

				result.next = l1;
				break;

			} else {

				if (l1.val == l2.val) {

					ListNode temp1 = new ListNode(l1.val);
					ListNode temp2 = new ListNode(l1.val);

					result.next = temp1;
					result = result.next;
					result.next = temp2;
					result = result.next;

					l1 = l1.next;
					l2 = l2.next;
				} else if (l1.val > l2.val) {
					ListNode temp = new ListNode(l2.val);
					result.next = temp;
					result = result.next;
					l2 = l2.next;
				} else {
					ListNode temp = new ListNode(l1.val);
					result.next = temp;
					result = result.next;
					l1 = l1.next;
				}
			}

		}

		return res.next;
	}
}
